package edu.isistan.matching.utils;

import edu.isistan.matching.scoreTypes.ComposeMatchScore;
import edu.isistan.matching.scoreTypes.ScoreMatrix;

public class KuhnsHungarianMethod {

	/**
	 * Este metodo recibe un MatchScore de tipo <b>Compose</b>, y calcula a
	 * partir del mismo la combinacion de elementos que maximise el resultado
	 * total. Además, almacena cuales son los elementos que producen dicho valor
	 * maximo. Dado un MatchScore compuesto, se busca las relaciones entre los
	 * elementos de la matriz ScoreMatrix asociada a él. Existen dos modos de
	 * ejecución, determinados mediante la booleana pasada por parámetro. El
	 * método húngaro el cual cada elemento está asociado a lo sumo a un
	 * elemento del otro conjunto. El método restante, cada elemento está
	 * asociado a al menos un elementos del otro conjunto, pudiendo existir
	 * elementos de un mismo conjunto asociados a un único elemento del segundo
	 * conjunto.
	 * 
	 * @param composeMatch
	 *            MatchScore que se analizará, el resultado se almacena en la
	 *            matriz ScoreMatrix asocada a el.
	 * @param bestAssigment
	 *            modo de ejecución. <b>true</b> indica Hungarian, <b>false</b>
	 *            asignación simple.
	 */
	public static void findAssigment(ComposeMatchScore composeMatch, boolean hungarianAssigment) {

		ScoreMatrix matrixRep = composeMatch.getChildScoreMatrix();
		if (matrixRep == null)
			return;

		double[][] doubleScoreMatrix = matrixRep.getDoubleValuesMatrix();

		if (doubleScoreMatrix == null || doubleScoreMatrix.length == 0)
			return;

		int[][] mappingPairs = null;
		if (hungarianAssigment) {
			mappingPairs = hungarianMapping(doubleScoreMatrix);
		} else {
			mappingPairs = simpleMapping(doubleScoreMatrix);
		}
		double[] resultMapping = new double[doubleScoreMatrix.length];
		// Obtenemos cual es el valor para cada Par de types.
		for (int i = 0; i < mappingPairs.length; i++) {
			resultMapping[i] = doubleScoreMatrix[mappingPairs[i][0]][mappingPairs[i][1]];
		}
		// Obtenemos la suma resultante de sumar los valores entre las distintos
		// Pares de WSDLElements
		double valueResult = ArrayFunctions.getSum(resultMapping);

		composeMatch.setScore(valueResult);
		matrixRep.setMappingValues(mappingPairs);

	}

	public static int[][] simpleMapping(double[][] array) {

		if (array.length == 0)
			return (new int[0][0]);

		int[][] assignment = new int[array.length][2];
		for (int i = 0; i < array.length; i++) {
			double maxValue = -1;
			int maxIndex = -1;
			for (int j = 0; j < array[i].length; j++) {
				if (maxValue < array[i][j]) {
					maxValue = array[i][j];
					maxIndex = j;
				}
			}
			if (maxIndex >= 0) {
				assignment[i][0] = i;
				assignment[i][1] = maxIndex;
			}
		}

		return assignment;
	}

	public static int[][] hungarianMapping(double[][] array) {

		boolean transpose = false;
		if (array.length > array[0].length) {
			array = ArrayFunctions.transpose(array);
			transpose = true;
		}
		String sumType = "max";
		// Invocamos al Algoritmo Hungarian
		int[][] assignment = hgAlgorithm(array, sumType, transpose);
		return assignment;
	}

	/** HUNGARIAN ALGORITHM */
	private static int[][] hgAlgorithm(double[][] array, String sumType, boolean traspose) {
		if (array.length == 0)
			return (new int[0][0]);
		double[][] cost = ArrayFunctions.copyOf(array);

		if (sumType.equalsIgnoreCase("max")) {
			double maxWeight = ArrayFunctions.findLargest(cost);
			for (int i = 0; i < cost.length; i++) {
				for (int j = 0; j < cost[i].length; j++) {
					cost[i][j] = maxWeight - cost[i][j];
				}
			}
		}
		// Find largest cost matrix element (needed for step 6).
		double maxCost = ArrayFunctions.findLargest(cost);

		int[][] mask = new int[cost.length][cost[0].length]; // The mask
		// array.
		int[] rowCover = new int[cost.length]; // The row covering vector.
		int[] colCover = new int[cost[0].length]; // The column covering
		// vector.
		int[] zero_RC = new int[2]; // Position of last zero from Step 4.
		int step = 1;
		boolean done = false;
		while (done == false) {
			switch (step) {
			case 1:
				step = hg_step1(step, cost);
				break;
			case 2:
				step = hg_step2(step, cost, mask, rowCover, colCover);
				break;
			case 3:
				step = hg_step3(step, mask, colCover);
				break;
			case 4:
				step = hg_step4(step, cost, mask, rowCover, colCover, zero_RC);
				break;
			case 5:
				step = hg_step5(step, mask, rowCover, colCover, zero_RC);
				break;
			case 6:
				step = hg_step6(step, cost, rowCover, colCover, maxCost);
				break;
			case 7:
				done = true;
				break;
			}
		}

		int[][] assignment = new int[array.length][2];

		for (int i = 0; i < mask.length; i++) {
			for (int j = 0; j < mask[i].length; j++) {
				if (mask[i][j] == 1) {
					if (traspose) {
						assignment[i][0] = j;
						assignment[i][1] = i;
					} else {
						assignment[i][0] = i;
						assignment[i][1] = j;
					}
				}
			}
		}
		return assignment;
	}

	/**
	 * STEP 1: For each row of the cost matrix, find the smallest element and
	 * subtract it from from every other element in its row
	 */
	private static int hg_step1(int step, double[][] cost) {
		double minval;
		for (int i = 0; i < cost.length; i++) {
			minval = cost[i][0];
			// 1st inner loop finds min val in row
			for (int j = 0; j < cost[i].length; j++) {
				if (minval > cost[i][j]) {
					minval = cost[i][j];
				}
			}
			// 2nd inner loop subtracts it
			for (int j = 0; j < cost[i].length; j++) {
				cost[i][j] = cost[i][j] - minval;
			}
		}
		step = 2;
		return step;
	}

	/**
	 * STEP 2: Marks uncovered zeros as starred and covers their row and column
	 */
	private static int hg_step2(int step, double[][] cost, int[][] mask, int[] rowCover, int[] colCover) {
		for (int i = 0; i < cost.length; i++) {
			for (int j = 0; j < cost[i].length; j++) {
				if ((cost[i][j] == 0) && (colCover[j] == 0) && (rowCover[i] == 0)) {
					mask[i][j] = 1;
					colCover[j] = 1;
					rowCover[i] = 1;
				}
			}
		}
		clearCovers(rowCover, colCover); // Reset cover vectors.
		step = 3;
		return step;
	}

	/**
	 * STEP 3: Cover columns of starred zeros. Check if all columns are covered
	 */
	private static int hg_step3(int step, int[][] mask, int[] colCover) {
		// Cover columns of starred zeros
		for (int i = 0; i < mask.length; i++) {
			for (int j = 0; j < mask[i].length; j++) {
				if (mask[i][j] == 1) {
					colCover[j] = 1;
				}
			}
		}
		int count = 0;
		// Check if all columns are covered.
		for (int j = 0; j < colCover.length; j++) {
			count = count + colCover[j];
		}
		// Should be cost.length but ok, because mask has same dimensions
		if (count >= mask.length) {
			step = 7;
		} else {
			step = 4;
		}
		return step;
	}

	/**
	 * STEP 4: Find an uncovered zero in cost and prime it (if none go to step
	 * 6). Check for star in same row: if yes, cover the row and uncover the
	 * star's column. Repeat until no uncovered zeros are left and go to step 6.
	 * If not, save location of primed zero and go to step 5
	 */
	private static int hg_step4(int step, double[][] cost, int[][] mask, int[] rowCover, int[] colCover, int[] zero_RC) {
		// Holds row and col of uncovered zero.
		int[] row_col = new int[2];
		boolean done = false;
		while (done == false) {
			row_col = findUncoveredZero(row_col, cost, rowCover, colCover);
			if (row_col[0] == -1) {
				done = true;
				step = 6;
			} else {
				mask[row_col[0]][row_col[1]] = 2; // Prime the found uncovered
				// zero.
				boolean starInRow = false;
				for (int j = 0; j < mask[row_col[0]].length; j++) {
					// If there is a star in the same row...
					if (mask[row_col[0]][j] == 1) {
						starInRow = true;
						row_col[1] = j; // remember its column.
					}
				}
				if (starInRow == true) {
					rowCover[row_col[0]] = 1; // Cover the star's row.
					colCover[row_col[1]] = 0; // Uncover its column.
				} else {
					zero_RC[0] = row_col[0]; // Save row of primed zero.
					zero_RC[1] = row_col[1]; // Save column of primed zero.
					done = true;
					step = 5;
				}
			}
		}
		return step;
	}

	/** Aux 1 for hg_step4 */
	private static int[] findUncoveredZero(int[] row_col, double[][] cost, int[] rowCover, int[] colCover) {
		row_col[0] = -1; // Just a check value. Not a real index.
		row_col[1] = 0;
		int i = 0;
		boolean done = false;
		while (done == false) {
			int j = 0;
			while (j < cost[i].length) {
				if (cost[i][j] == 0 && rowCover[i] == 0 && colCover[j] == 0) {
					row_col[0] = i;
					row_col[1] = j;
					done = true;
				}
				j = j + 1;
			}
			i = i + 1;
			if (i >= cost.length) {
				done = true;
			}
		}
		return row_col;
	}

	/**
	 * STEP 5: Construct series of alternating primes and stars. Start with
	 * prime from step 4. Take star in the same column. Next take prime in the
	 * same row as the star. Finish at a prime with no star in its column.
	 * Unstar all stars and star the primes of the series. Erasy any other
	 * primes. Reset covers. Go to step 3
	 */
	private static int hg_step5(int step, int[][] mask, int[] rowCover, int[] colCover, int[] zero_RC) {
		int count = 0; // Counts rows of the path matrix.
		int[][] path = new int[(mask[0].length * mask.length)][2]; // Path
		// matrix
		// (stores
		// row and
		// col).
		path[count][0] = zero_RC[0]; // Row of last prime.
		path[count][1] = zero_RC[1]; // Column of last prime.

		boolean done = false;
		while (done == false) {
			int r = findStarInCol(mask, path[count][1]);
			if (r >= 0) {
				count = count + 1;
				path[count][0] = r; // Row of starred zero.
				path[count][1] = path[count - 1][1]; // Column of starred
				// zero.
			} else {
				done = true;
			}
			if (done == false) {
				int c = findPrimeInRow(mask, path[count][0]);
				count = count + 1;
				path[count][0] = path[count - 1][0]; // Row of primed zero.
				path[count][1] = c; // Col of primed zero.
			}
		}
		convertPath(mask, path, count);
		clearCovers(rowCover, colCover);
		erasePrimes(mask);
		step = 3;
		return step;
	}

	/** Aux 1 for hg_step5 */
	private static int findStarInCol(int[][] mask, int col) {
		int r = -1; // Again this is a check value.
		for (int i = 0; i < mask.length; i++) {
			if (mask[i][col] == 1) {
				r = i;
			}
		}
		return r;
	}

	/** Aux 2 for hg_step5 */
	private static int findPrimeInRow(int[][] mask, int row) {
		int c = -1;
		for (int j = 0; j < mask[row].length; j++) {
			if (mask[row][j] == 2) {
				c = j;
			}
		}
		return c;
	}

	/** Aux 3 for hg_step5 */
	private static void convertPath(int[][] mask, int[][] path, int count) {
		for (int i = 0; i <= count; i++) {
			if (mask[(path[i][0])][(path[i][1])] == 1) {
				mask[(path[i][0])][(path[i][1])] = 0;
			} else {
				mask[(path[i][0])][(path[i][1])] = 1;
			}
		}
	}

	/** Aux 4 for hg_step5 */
	private static void erasePrimes(int[][] mask) {
		for (int i = 0; i < mask.length; i++) {
			for (int j = 0; j < mask[i].length; j++) {
				if (mask[i][j] == 2) {
					mask[i][j] = 0;
				}
			}
		}
	}

	/** Aux 5 for hg_step5 (and not only) */
	private static void clearCovers(int[] rowCover, int[] colCover) {
		for (int i = 0; i < rowCover.length; i++) {
			rowCover[i] = 0;
		}
		for (int j = 0; j < colCover.length; j++) {
			colCover[j] = 0;
		}
	}

	/**
	 * STEP 6: Find smallest uncovered value in cost: a. Add it to every element
	 * of covered rows b. Subtract it from every element of uncovered columns.
	 * Go to step 4
	 */
	private static int hg_step6(int step, double[][] cost, int[] rowCover, int[] colCover, double maxCost) {
		double minval = findSmallest(cost, rowCover, colCover, maxCost);
		for (int i = 0; i < rowCover.length; i++) {
			for (int j = 0; j < colCover.length; j++) {
				if (rowCover[i] == 1) {
					cost[i][j] = cost[i][j] + minval;
				}
				if (colCover[j] == 0) {
					cost[i][j] = cost[i][j] - minval;
				}
			}
		}
		step = 4;
		return step;
	}

	/** Aux 1 for hg_step6 */
	private static double findSmallest(double[][] cost, int[] rowCover, int[] colCover, double maxCost) {
		double minval = maxCost; // There cannot be a larger cost than this.
		for (int i = 0; i < cost.length; i++) {
			for (int j = 0; j < cost[i].length; j++) {
				if (rowCover[i] == 0 && colCover[j] == 0 && (minval > cost[i][j])) {
					minval = cost[i][j];
				}
			}
		}
		return minval;
	}

	public static void scoreOfBestAssigment(ComposeMatchScore composeMatch) {

		findAssigment(composeMatch, true);
	}

}
